package sort.impl;

import sort.BaseSort;

public class MergeSort implements BaseSort {
    @Override
    public void safeSort(Comparable[] arr) {
        merge(arr);
    }

    private void merge(Comparable[] arr, int start1, int end1, int start2, int end2){
        int left1 = start1, left2 = start2;
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        int len = len1 + len2;
        Comparable[] temp = new Comparable[len];
        int tempIndex = 0;
        while(start1 <= end1 && start2 <= end2){
            if(arr[start1].compareTo(arr[start2]) <= 0){
                temp[tempIndex++] = arr[start1];
                start1++;
            }else{
                temp[tempIndex++] = arr[start2];
                start2++;
            }
        }
        while(start1 <= end1){
            temp[tempIndex++] = arr[start1++];
        }
        while (start2 <= end2){
            temp[tempIndex++] = arr[start2++];
        }
        int index = 0;
        for(int i = left1; i <= end1; i++){
            arr[i] = temp[index++];
        }
        for(int i = left2; i <= end2; i++){
            arr[i] = temp[index++];
        }
    }

    private void mergeRecursion(Comparable[] arr, int start, int end){
        if(start == end){
            return;
        }else{
            int mid = (start + end) / 2;
            mergeRecursion(arr, start, mid);
            mergeRecursion(arr, mid + 1, end);
            merge(arr, start, mid, mid + 1, end);
        }
    }

    private void merge(Comparable[] arr){
        int start = 0, end = arr.length - 1;
        mergeRecursion(arr, start, end);
    }
}
